一.定义

第二类斯特林数 $\begin{Bmatrix}n\\m\end{Bmatrix}$ 表示把 $n$ 个不同的小球放进 $m$ 个相同的盒子里，不能有空盒的方案数。

一些小性质：

• $\begin{Bmatrix}n\\0\end{Bmatrix}=[n=0]$
• 当 $n<m$ ，$\begin{Bmatrix}n\\m\end{Bmatrix}=0$

二.一些等式

1. 递推式：$\begin{Bmatrix}n\\m\end{Bmatrix}=\begin{Bmatrix}n-1\\m-1\end{Bmatrix}+m\begin{Bmatrix}n-1\\m\end{Bmatrix}$

对第 $n$ 个球的放法讨论

1. 单独放一个盒子，方案为 $\begin{Bmatrix}n-1\\m-1\end{Bmatrix}$
2. 与其他球放在一个盒子，因为盒子不同有 $m$ 种选法，每种选法方案为 $\begin{Bmatrix}n-1\\m\end{Bmatrix}$

2.自然幂数和：$m^n=\sum_{i=0}^n \begin{Bmatrix}n\\i\end{Bmatrix} m^{\underline i}=\sum_{i=0}^n \begin{Bmatrix}n\\i\end{Bmatrix} \binom{m}{i} i!$

1.组合意义

左式为将 $n$ 不同的小球放进 $m$ 个不同的盒子里。

右式枚举非空盒子的数量 $i$，选盒子的方案数为 $\binom m i$ ， 将 $n$ 个不同的球放入 $i$ 个盒子方案数为 $\begin{Bmatrix}n\\i\end{Bmatrix}$，因为盒子不同所以有 $i!$ 种排列。

2.例题

1.CF932E Team Work

2.P4091 [HEOI2016/TJOI2016]求和

3.P4827 [国家集训队] Crash 的文明世界 & SP7363 TREESUM - Tree Sum

4.CF961G Partitions

5.CF1097G

3.通项公式：$\begin{Bmatrix}n\\m\end{Bmatrix}= \frac{1}{m!}\sum_{i=0}^m \left(-1\right)^i \binom {m}{i} \left(m-i\right)^n$

1.证明

设 $f(m)=m^n,g(m)=\begin{Bmatrix}n\\m\end{Bmatrix} m!$。

那么有： $f(m)=\sum_{i=0}^m \binom m i \begin{Bmatrix}n\\i\end{Bmatrix} i!=\sum_{i=0}^m \binom m i g(i)$

这里上界为 $m$ 不影响答案，因为 $n<m$ 时 $\begin{Bmatrix}n\\i\end{Bmatrix}=0$。

然后由二项式反演得： $g(m)=\sum_{i=0}^m (-1)^{m-i}\binom m i f(i)$

$\begin{Bmatrix}n\\m\end{Bmatrix} m!=\sum_{i=0}^m (-1)^{m-i}\binom m i i^n$

$\begin{Bmatrix}n\\m\end{Bmatrix}=\frac{1}{m!}\sum_{i=0}^m (-1)^{m-i}\binom m i i^n$

$\begin{Bmatrix}n\\m\end{Bmatrix}=\frac{1}{m!}\sum_{i=0}^m (-1)^{i}\binom m i (m-i)^n$

2.应用 P5395 第二类斯特林数·行

$\begin{Bmatrix}n\\m\end{Bmatrix} m!=\sum_{i=0}^m (-1)^{m-i}\binom m i i^n$

$\begin{Bmatrix}n\\m\end{Bmatrix} m!=\sum_{i=0}^m (-1)^{m-i} \frac{m!}{i! (m-i)!} i^n$

$\begin{Bmatrix}n\\m\end{Bmatrix}=\sum_{i=0}^m \frac{(-1)^{m-i}i^n}{i!(m-i)!}$

$\begin{Bmatrix}n\\m\end{Bmatrix}=\sum_{i=0}^m \frac{i^n}{i!} \frac{(-1)^{m-i}}{(m-i)!}$

可以看出是一个卷积形式，用多项式乘法可 $\mathcal{O(n \log n)}$ 求出第二类斯特林数的任意一行。

三.生成函数